/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package hojano6;
import java.util.Vector;
/**
 *
 * @author Magaly
 */
public class HuffmanHeap {
    
    //------------------------------------------------------------------------
    // Atributos:
    //------------------------------------------------------------------------
    
    // La informaciÃ³n que se tendra en el heap.
    private Vector<ArbolHuffman> data;
    
    //------------------------------------------------------------------------
    // Constructores
    //------------------------------------------------------------------------

    /**
     * Constructor que crea un heap vacio.
     * @pre: -
     * @post: Construye un nuevo priority queue.
     */
    public HuffmanHeap(){
        this.data=new Vector <ArbolHuffman > ();
    }
    
    /**
     * Constructor que crea un heap a partir de un vector.
     * @pre: -
     * @post: Construye un nuevo priority queue de un vector ya hecho.
     */
    public HuffmanHeap (Vector<ArbolHuffman> data){
        int i;
        this.data = new Vector <ArbolHuffman> (data.size());
        for (i=0; i< data.size(); i++){
            add(data.get(i));
        }
    }
    
    //------------------------------------------------------------------------
    // MÃ©todos
    //------------------------------------------------------------------------

    /**
     * MÃ©todo que determina la ubicaciÃ³n del padre del nodo.
     * @ pre: Mayor a cero y menor al tamaÃ±o.
     * @post: Regresa la la ubicaciÃ³n del padre del nodo.
     * @param i
     */
    protected static int parent (int i){
        return (i-1)/2;
    }
    
    /**
     * MÃ©todo que determina la ubicaciÃ³n del hijo izquierdo del nodo.
     * @ pre: Mayor a cero y menor al tamaÃ±o.
     * @post: Regresa la la ubicaciÃ³n del hijo izquierdo del nodo.
     * @param i
     */
    protected static int left (int i){
        return 2*i+1;
    }
   
    /**
     * MÃ©todo que determina la ubicaciÃ³n del hijo derecho del nodo.
     * @ pre: Mayor a cero y menor al tamaÃ±o.
     * @post: Regresa la la ubicaciÃ³n del hijo derecho del nodo.
     * @param i
     */
    protected static int right (int i){
        return 2*(i+1);
    }
    
    /**
     * MÃ©todo que toma un indice de un valor que puede estar fuera de lugar y
     * lo manda hacia arriba a la raiz hasta que llegue al lugar correcto.
     * @pre: Mayor que cero y menor que el tamaÃ±o.
     * @post: Mueve el nodo al index leaf arriba a la apropiada posiciÃ³n.
     * @param leaf 
     */
    protected void percolateUp (int leaf){
        int parent = parent (leaf);
        ArbolHuffman value = this.data.get(leaf);
        while ((leaf > 0) && (value.root.value().compareTo(this.data.get(parent).root.value())<0)){
            this.data.set(leaf, this.data.get(parent));
            leaf = parent;
            parent = parent (leaf);
        }
        this.data.set(leaf, value);
    }
   
    /**
     * MÃ©todo que permite agregar un valor.
     * @pre: El valor no es nulo.
     * @post: Se agrega el valor.
     * @param value 
     */
    public void add(ArbolHuffman value){
        this.data.add(value);
        percolateUp (data.size()-1);
    }
    
    /**
     * MÃ©todo que empuja un valor grande para abajo hasta el heap mÃ¡s pequeÃ±o.
     * @pre: Mayor que cero y menor que el tamaÃ±o.
     * @post: Mueve el nodo al indice de la raiz abajo.
     * @param root 
     */
    protected void pushDownRoot (int root){
        int heapSize = this.data.size();
        ArbolHuffman value = data.get(root);
        while (root < heapSize) {
            int childpos = left (root);
            if (childpos < heapSize){
                if ((right(root)< heapSize)&&
                   ((this.data.get(childpos+1)).root.value().compareTo(this.data.get(childpos).root.value())< 0)){
                    childpos++;
                }
                // Si pasa, childpos es el indice mÃ¡s pequeÃ±o de los dos hijos.
                if ((this.data.get(childpos)).root.value().compareTo(value.root.value())< 0){
                    data.set(root, this.data.get(childpos));
                    root = childpos; // Sigue moviendose para abajo
                }else{
                    //encontro la posiciÃ³n derecha.
                    this.data.set(root, value);
                    return;
                }
            }else{
                data.set(root, value);
                return;
            }
        }
    }   
    
    /**
     * MÃ©todo que permite remover el valor mÃ­nimo en el heap.
     * @pre: Deben haber valores.
     * @post: Se remueve del heap el valor mÃ¡s pequeÃ±o.
     * @return minVal
     */
    public ArbolHuffman remove (){
        ArbolHuffman minVal = this.data.get(0);
        this.data.set(0, this.data.get(this.data.size()-1));
        this.data.setSize(this.data.size()-1);
        if (data.size()>1){
            pushDownRoot(0);
        }
        return minVal;
    }

    /**
     * MÃ©todo que permite obtener el vector con los datos.
     * @pre: -
     * @post: Obiene el vector.
     * @return data 
     */
    public Vector<ArbolHuffman> getData() {
        return data;
    }

    
}
